import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    //帮助判断变化后的字符串是否是有效的
    HashMap<String, Boolean> bankMap = new HashMap<>();
    //帮助判断变化后的字符串是否已经判断过了
    HashMap<String, Boolean> isTraverse = new HashMap<>();
    Queue<String> q = new LinkedList<>();

    public int minMutation(String startGene, String endGene, String[] bank) {
        // int len = bank.length;

        for (String str : bank) {
            bankMap.put(str, true);
        }

        isTraverse.put(startGene, true);
        q.offer(startGene);

        char[] change = {'A', 'C', 'G', 'T'};

        int ret = 0;
        if (startGene.equals(endGene)) {
            return 0;
        }

        if (!bankMap.containsKey(endGene)) {
            return -1;
        }

        while (!q.isEmpty()) {
            ret++;
            int size = q.size();
            while (size > 0) {
                size--;
                String str = q.poll();
                //遍历整个字符串
                for (int i = 0; i < 8; i++) {
                    char[] ch = str.toCharArray();
                    //找到替换后的所有可能结果
                    for (int j = 0; j < 4; j++) {
                        ch[i] = change[j];
                        String s = new String(ch);
                        if (s.equals(endGene)) {
                            return ret;
                        }
                        if (bankMap.containsKey(s) && !isTraverse.containsKey(s)) {
                            isTraverse.put(s, true);
                            q.offer(s);
                        }
                    }
                }
            }
        }

        return -1;
    }
}
